package demo5;

/**
 * Created with IntelliJ IDEA.
 * Description:平衡二叉树
 * User: liangyuanzhang
 * Date: 2025-4-22
 * Time: 22:33
 */
//下面算法的时间复杂度是O(N^2),要想改成O(N),可以再计算每个节点的高度的时候看是否平衡，不平衡返回-1
//平衡二叉树 --> 左右子树高度相差不超过1(<=1)
//如果一棵树 是平衡二叉树 那么 他的每颗子树 都是平衡二叉树
class Test {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        //Math.abs () 是用于获取数值绝对值的函数
        return Math.abs(leftHeight-rightHeight) < 2
                && isBalanced(root.left) && isBalanced(root.right);
    }

    public int getHeight(TreeNode root) {
        if(root == null) return 0;
        //获取一棵树的高度-->取左右子树高度的最大值+1
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.max(leftHeight,rightHeight) + 1;
    }





    // 定义方法isBalanced2，用于判断以root为根节点的二叉树是否平衡，返回值为boolean类型
    public boolean isBalanced2(TreeNode root) {
        // 如果根节点root为空，说明这棵树为空树，空树是平衡的，直接返回true
        if(root == null) return true;
        // 调用getHeight2方法获取树的高度相关信息，若返回值大于等于0，说明树是平衡的，返回true；否则返回false
        return getHeight2(root) >= 0;
    }



    // 定义方法getHeight2，用于获取以root为根节点的二叉树的高度，返回值为int类型
    public int getHeight2(TreeNode root) {
        // 如果根节点root为空，说明这棵子树为空树，空树高度为0，返回0
        if(root == null) {
            return 0;
        }
        // 递归调用getHeight2方法，获取当前节点左子树的高度
        int leftHeight = getHeight2(root.left);
        // 如果左子树高度小于0，说明左子树已经不平衡，直接返回-1表示整棵树不平衡
        if(leftHeight < 0) {
            return -1;
        }
        // 递归调用getHeight2方法，获取当前节点右子树的高度
        int rightHeight = getHeight2(root.right);
        // 如果右子树高度大于等于0，并且左右子树高度差的绝对值小于等于1，说明当前子树是平衡的
        // 此时返回左右子树中较大的高度加1，作为当前子树的高度
        if(rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
            // 否则（右子树高度小于0或者左右子树高度差绝对值大于1），说明当前子树不平衡，返回-1
            return -1;
        }
    }


}
/*
思路：
遍历当前这棵树的每个节点，求每个节点的左树和右树的高度，如果发现h>=2，则返回false
&& root的左树也是平衡的 && root的右树也是平衡的
*/



